package algorithm.BagKindCount;

/*
背包容量为w
一共有n袋零食，第i袋零食体积为v[i]
求总体积不超过背包的容量下，一共有多少种零食放法
 */
public class BagKindCount {

    public static int getCount(int idx, int limit, int[] v) {
        if (idx == v.length-1) {
            if (v[idx] > limit) {
                return 1;
            }
            return 2;
        }

        int p1 = getCount(idx+1, limit, v);
        int p2 = 0;
        if (limit-v[idx] > 0) {
            p2 = getCount(idx + 1, limit - v[idx], v);
        }
        return p1+p2;
    }

    public static int dp(int limit, int[] v) {
        int[][] dp = new int[v.length][limit+1];
        for (int i = 0; i < limit+1; i++) {
            if (v[v.length-1] <= i)
                dp[v.length-1][i] = 2;
            else
                dp[v.length-1][i] = 1;
        }
        for (int i = v.length-2; i >= 0; i--) {
            for (int j = 0; j < limit+1; j++) {
                if (j < v[i]) {
                    dp[i][j] = dp[i+1][j];
                } else {
                    dp[i][j] = dp[i+1][j] + dp[i+1][j-v[i]];
                }
            }
        }
        return dp[0][limit];
    }

    public static void main(String[] args) {
        int[] v = {1,3,5,1};
        int w = 10;
        int count = getCount(0, w, v);
//        int count = dp(w, v);
        System.out.println(count);
    }
}
